package com.c2b.algorithm.leetcode.base.monotone_stack;

import com.c2b.algorithm.leetcode.base.ListNode;
import com.c2b.algorithm.leetcode.base.Printer;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <a href="https://leetcode.cn/problems/next-greater-node-in-linked-list/">链表中的下一个更大节点(Next Greater Node In Linked List)</a>
 * <p>给定一个长度为 n 的链表 head</p>
 * <p>对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。</p>
 * <p>返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [2,1,5]
 *      输出：[5,5,0]
 *
 * 示例 2：
 *      输入：head = [2,7,4,3,5]
 *      输出：[7,0,5,5,0]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>链表中节点数为 n</li>
 *     <li>1 <= n <= 10^4</li>
 *     <li>1 <= Node.val <= 10^9</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/6 13:47
 */
public class LC1019NextGreaterNodeInLinkedList_M {

    static class Solution {
        /**
         * 单调栈
         */
        public int[] nextLargerNodes(ListNode head) {
            ListNode currNode;
            int length = 0;
            // 计算链表的长度
            for (currNode = head; currNode != null; currNode = currNode.next) {
                length++;
            }
            int[] ans = new int[length];
            currNode = head;
            // int[0]-值
            // int[1]-下标，从0开始
            Deque<int[]> stack = new ArrayDeque<>();
            for (int idx = 0; idx < length; idx++) {
                int currNodeVal = currNode.val;
                while (!stack.isEmpty() && currNodeVal > stack.peekLast()[0]) {
                    int[] ints = stack.pollLast();
                    ans[ints[1]] = currNodeVal;
                }
                stack.offerLast(new int[]{currNodeVal, idx});
                currNode = currNode.next;
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode listNode = new ListNode(1);
        listNode.next = new ListNode(7);
        listNode.next.next = new ListNode(5);
        listNode.next.next.next = new ListNode(1);
        listNode.next.next.next.next = new ListNode(9);
        listNode.next.next.next.next.next = new ListNode(2);
        listNode.next.next.next.next.next.next = new ListNode(5);
        listNode.next.next.next.next.next.next.next = new ListNode(1);
        int[] ints = solution.nextLargerNodes(listNode);
        Printer.printArrayInt(ints);
    }
}
